package com.zlk.algorithm.dataStructure.tree.treeBase;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName SuccessorNode
 * @description:查找后继节点
 * @author: slfang
 * @create: 2024-02-18 19:43
 * @Version 1.0
 **/
public class SuccessorNode {

    //中序遍历的后一位就是当前节点后继节点
    //中序遍历时间复杂度，可以利用parent指针优化到o(k) k指当前节点到后继节点长度

    //后继节点情况
    // 1、有右子树 ，找右子树中最左孩子
    // 2、无右子树 ，向父节点查找，直到父节点存在左孩子

    @Test
    public void test(){
        Node head = new Node(6);
        head.parent = null;
        head.left = new Node(3);
        head.left.parent = head;
        head.left.left = new Node(1);
        head.left.left.parent = head.left;
        head.left.left.right = new Node(2);
        head.left.left.right.parent = head.left.left;
        head.left.right = new Node(4);
        head.left.right.parent = head.left;
        head.left.right.right = new Node(5);
        head.left.right.right.parent = head.left.right;
        head.right = new Node(9);
        head.right.parent = head;
        head.right.left = new Node(8);
        head.right.left.parent = head.right;
        head.right.left.left = new Node(7);
        head.right.left.left.parent = head.right.left;
        head.right.right = new Node(10);
        head.right.right.parent = head.right;

        Node test = head.left.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.left.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.right.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.left.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.right; // 10's next is null
        System.out.println(test.value + " next: " + getSuccessorNode(test));

    }

    private Node getSuccessorNode(Node node) {
        if(node==null){
            return node;
        }
        if(node.right!=null){// 有右子树
            Node cur = node.right;
            while (cur.left!=null){
               cur = cur.left;
            }
            return cur;
        }else{//无右子树
            Node cur = node;
            Node parent = cur.parent;
            while (parent!=null&&parent.left!=cur){
                cur = parent;
                parent = cur.parent;
            }
            return parent;
        }
    }

    public  class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }


}
